package leetcode.search;

/**
 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。

 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 同一个单元格内的字母不允许被重复使用。

 */
public class Exist79 {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n =board[0].length;
        boolean [][]visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean b = find(board, visit, i, j, word, 0);
                if(b)
                    return true;
            }
        }
        return false;
    }


    private boolean find(char[][]board, boolean [][]visit,int i,int j,String str,int pos){
        int m = board.length;
        int n =board[0].length;

        if(pos==str.length())//已经匹配完了
            return true;

        if(i>=m || i<0 ||j>=n ||j<0 || visit[i][j] || str.charAt(pos)!=board[i][j])//越界或走过了或匹配不上了
            return false;

        visit[i][j] = true;//修改状态

        boolean hasPath = find(board,visit,i-1,j,str,pos+1) ||
                          find(board,visit,i+1,j,str,pos+1) ||
                          find(board,visit,i,j-1,str,pos+1) ||
                          find(board,visit,i,j+1,str,pos+1) ;

        //修改状态
        visit[i][j] = false;


        return hasPath;
    }

}